#include <iostream>
#include <cmath>
#include <vector>

double g(double t, double g_i)
{
    return std::pow((1.0 + t * (g_i - 1.0)) / (1.0 - t), 1.0/t);
}

// the derivative of g
inline double f(double t, double g_i)
{
    return -(std::pow(((-1.0 + (1.0 - g_i) * t)/(-1.0 + t)) , (1.0/t) ) * (g_i * t + (-1.0 + (2.0 - g_i) * t + (-1.0 + g_i)* t * t) * std::log((1.0 + (-1.0 + g_i) * t)/(1.0 - t)))) / ((-1.0 + t) * (1.0 + (-1.0 + g_i) * t) * t * t);
}


double Binary_Search(double l_range, double r_range, double g_i)
{
    double l = l_range;
    double r = r_range;
    double l_value = f(l, g_i);
    double r_value = f(r, g_i);
    double mid = (l + r) / 2.0;
    double mid_value = f(mid, g_i);
    double loop = 0;
    if(l_value * r_value > 0)
    {
        return l;
        std::cout << "BS2 error!" << std::endl;
    }
    while(loop <= 1e8)
    {
        if(mid_value >= 0)
        {
            r = mid;
            r_value = mid_value;
            mid = (l+r) / 2.0;
            mid_value = f(mid, g_i);
        }
        else
        {
            l = mid;
            l_value = mid_value;
            mid = (l+r)/2.0;
            mid_value = f(mid, g_i);
        }
        loop++;
        if(std::abs(f(mid, g_i)) <= 1e-10)
        {
            break;
        }
        if(l_value * r_value > 0)
        {
            std::cout << "BS1 error!" << std::endl;
            break;
        }
    }
    return mid;
}

int main()
{
    int input = 10000;
    double d = 1.0 * input;
    std::vector<double> G(input+1);
    G[0] = 1.0;
    for(int i=1;i<=input;i++)
    {
        double x = Binary_Search(1.0/d, 1.0-1.0/d, G[i-1]);
        std::cout << "x is " << x;
        std::cout << ", ratio is "  << std::pow(g(x, G[i-1]), 1.0/d) << std::endl;
        G[i] = G[i-1] * std::pow(g(x, G[i-1]), 1.0/d);
        if(i%100 == 0)
        {
            std::cout << "The program is running, " << i << "-th loop is finished..." << std::endl;
        }
    }
    std::cout << G[input] << std::endl;


    return 0;
}